<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/Frog_32px_1177822_easyicon.net.ico">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/Frog_32px_1177822_easyicon.net.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/Frog_16px_1177822_easyicon.net.ico">
  <link rel="mask-icon" href="/images/Frog_32px_1177822_easyicon.net.ico" color="#222">

<link rel="stylesheet" href="/css/main.css">


<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">
  <link rel="stylesheet" href="/lib/pace/pace-theme-minimal.min.css">
  <script src="/lib/pace/pace.min.js"></script>

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"hxy1997.xyz","root":"/","scheme":"Pisces","version":"7.8.0","exturl":false,"sidebar":{"position":"left","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":true,"pangu":false,"comments":{"style":"tabs","active":"valine","storage":true,"lazyload":true,"nav":null,"activeClass":"valine"},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"输入关键字","hits_empty":"没有找到与「${query}」相关搜索","hits_stats":"${hits} 条相关记录，共耗时 ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.json"};
  </script>

  <meta name="description" content="按照算法和数据结构进行分类，一起来刷题，用于自己在面试前查漏补缺。我的意向岗位是前端，选择用javascript来刷题，优点是动态语言，语法简单，缺点是遇见复杂数据结构会出现较难的写法，如堆、并查集，每题对应leetcode的题号。本篇是BFS、DFS 回溯法">
<meta property="og:type" content="article">
<meta property="og:title" content="BFS、DFS 回溯法刷题">
<meta property="og:url" content="https://hxy1997.xyz/2021/03/09/BFS%E3%80%81DFS%20%E5%9B%9E%E6%BA%AF%E6%B3%95%E5%88%B7%E9%A2%98/index.html">
<meta property="og:site_name" content="hxy的博客">
<meta property="og:description" content="按照算法和数据结构进行分类，一起来刷题，用于自己在面试前查漏补缺。我的意向岗位是前端，选择用javascript来刷题，优点是动态语言，语法简单，缺点是遇见复杂数据结构会出现较难的写法，如堆、并查集，每题对应leetcode的题号。本篇是BFS、DFS 回溯法">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210710154048.png">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210419095805.jpeg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210419095744.jpeg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210711174412.jpeg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210711174506.jpeg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210711174617.jpeg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210716080758.jpeg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210716080814.jpeg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210803000409.jpeg">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210803083157.jpeg">
<meta property="article:published_time" content="2021-03-08T16:02:39.000Z">
<meta property="article:modified_time" content="2021-08-03T00:47:23.848Z">
<meta property="article:author" content="hxy">
<meta property="article:tag" content="javascript">
<meta property="article:tag" content="数据结构和算法">
<meta property="article:tag" content="BFS、DFS 回溯法">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210710154048.png">

<link rel="canonical" href="https://hxy1997.xyz/2021/03/09/BFS%E3%80%81DFS%20%E5%9B%9E%E6%BA%AF%E6%B3%95%E5%88%B7%E9%A2%98/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>BFS、DFS 回溯法刷题 | hxy的博客</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

<link rel="alternate" href="/atom.xml" title="hxy的博客" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">hxy的博客</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">Mia san Mia!</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>
  <div class="reading-progress-bar"></div>

  <a href="https://github.com/huxingyi1997" class="github-corner" title="Follow me on GitHub" aria-label="Follow me on GitHub" rel="noopener" target="_blank"><svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://hxy1997.xyz/2021/03/09/BFS%E3%80%81DFS%20%E5%9B%9E%E6%BA%AF%E6%B3%95%E5%88%B7%E9%A2%98/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/Robben.gif">
      <meta itemprop="name" content="hxy">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="hxy的博客">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          BFS、DFS 回溯法刷题
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2021-03-09 00:02:39" itemprop="dateCreated datePublished" datetime="2021-03-09T00:02:39+08:00">2021-03-09</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2021-08-03 08:47:23" itemprop="dateModified" datetime="2021-08-03T08:47:23+08:00">2021-08-03</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/%E5%88%B7%E9%A2%98/" itemprop="url" rel="index"><span itemprop="name">刷题</span></a>
                </span>
            </span>

          
            <span class="post-meta-item" title="热度" id="busuanzi_container_page_pv" style="display: none;">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">热度：</span>
              <span id="busuanzi_value_page_pv"></span>
            </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2021/03/09/BFS%E3%80%81DFS%20%E5%9B%9E%E6%BA%AF%E6%B3%95%E5%88%B7%E9%A2%98/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2021/03/09/BFS%E3%80%81DFS%20%E5%9B%9E%E6%BA%AF%E6%B3%95%E5%88%B7%E9%A2%98/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <p>按照算法和数据结构进行分类，一起来刷题，用于自己在面试前查漏补缺。我的意向岗位是前端，选择用javascript来刷题，优点是动态语言，语法简单，缺点是遇见复杂数据结构会出现较难的写法，如堆、并查集，每题对应leetcode的题号。本篇是BFS、DFS 回溯法</p>
<span id="more"></span>

<h2 id="专题部分"><a href="#专题部分" class="headerlink" title="专题部分"></a>专题部分</h2><h3 id="BFS、DFS-回溯法"><a href="#BFS、DFS-回溯法" class="headerlink" title="BFS、DFS 回溯法"></a>BFS、DFS 回溯法</h3><h4 id="17-电话号码的字母组合"><a href="#17-电话号码的字母组合" class="headerlink" title="17. 电话号码的字母组合"></a>17. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/">电话号码的字母组合</a></h4><p>给定一个仅包含数字 <code>2-9</code> 的字符串，返回所有它能表示的字母组合。答案可以按 <strong>任意顺序</strong> 返回。</p>
<p>给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。</p>
<p><img data-src="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210710154048.png" alt="img"></p>
<p> <strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：digits &#x3D; &quot;23&quot;</span><br><span class="line">输出：[&quot;ad&quot;,&quot;ae&quot;,&quot;af&quot;,&quot;bd&quot;,&quot;be&quot;,&quot;bf&quot;,&quot;cd&quot;,&quot;ce&quot;,&quot;cf&quot;]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：digits &#x3D; &quot;&quot;</span><br><span class="line">输出：[]</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：digits &#x3D; &quot;2&quot;</span><br><span class="line">输出：[&quot;a&quot;,&quot;b&quot;,&quot;c&quot;]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>0 &lt;= digits.length &lt;= 4</code></li>
<li><code>digits[i]</code> 是范围 <code>[&#39;2&#39;, &#39;9&#39;]</code> 的一个数字。</li>
</ul>
<p>使用回溯发怎么保存结果，可以数组保存路径</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string&#125;</span> <span class="variable">digits</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;string[]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">let</span> letterMap = [ </span><br><span class="line">    <span class="string">&quot; &quot;</span>,    <span class="comment">// 0</span></span><br><span class="line">    <span class="string">&quot;&quot;</span>,     <span class="comment">// 1</span></span><br><span class="line">    <span class="string">&quot;abc&quot;</span>,  <span class="comment">// 2</span></span><br><span class="line">    <span class="string">&quot;def&quot;</span>,  <span class="comment">// 3</span></span><br><span class="line">    <span class="string">&quot;ghi&quot;</span>,  <span class="comment">// 4</span></span><br><span class="line">    <span class="string">&quot;jkl&quot;</span>,  <span class="comment">// 5</span></span><br><span class="line">    <span class="string">&quot;mno&quot;</span>,  <span class="comment">// 6</span></span><br><span class="line">    <span class="string">&quot;pqrs&quot;</span>, <span class="comment">// 7</span></span><br><span class="line">    <span class="string">&quot;tuv&quot;</span>,  <span class="comment">// 8</span></span><br><span class="line">    <span class="string">&quot;wxyz&quot;</span>  <span class="comment">// 9</span></span><br><span class="line">];</span><br><span class="line"><span class="keyword">var</span> letterCombinations = <span class="function"><span class="keyword">function</span>(<span class="params">digits</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (digits.length === <span class="number">0</span>) <span class="keyword">return</span> [];</span><br><span class="line">    <span class="keyword">let</span> res = [];</span><br><span class="line">    <span class="keyword">let</span> aux = [];</span><br><span class="line">    <span class="keyword">let</span> len = digits.length;</span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">backTrack</span> (<span class="params">index</span>) </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index === len) &#123;</span><br><span class="line">            res.push([...aux].join(<span class="string">&#x27;&#x27;</span>));</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">let</span> digit = digits[index];</span><br><span class="line">        <span class="keyword">let</span> string = letterMap[digit];</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">let</span> i = <span class="number">0</span> ; i &lt; string.length ; i++) &#123;</span><br><span class="line">            aux.push(string[i]);</span><br><span class="line">            backTrack(index + <span class="number">1</span>);</span><br><span class="line">            aux.pop();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    backTrack(<span class="number">0</span>);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="22-括号生成"><a href="#22-括号生成" class="headerlink" title="22. 括号生成"></a>22. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/generate-parentheses/">括号生成</a></h4><p>数字 <code>n</code> 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 <strong>有效的</strong> 括号组合。 </p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 3</span><br><span class="line">输出：[&quot;((()))&quot;,&quot;(()())&quot;,&quot;(())()&quot;,&quot;()(())&quot;,&quot;()()()&quot;]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 1</span><br><span class="line">输出：[&quot;()&quot;]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= n &lt;= 8</code></li>
</ul>
<p>同时记录<code>(</code>和<code>)</code>的数量</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">n</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;string[]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> generateParenthesis = <span class="function"><span class="keyword">function</span>(<span class="params">n</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (n == <span class="number">0</span>) <span class="keyword">return</span> [];</span><br><span class="line">    <span class="comment">// 记录所有合法的括号组合</span></span><br><span class="line">    <span class="keyword">let</span> res = [];</span><br><span class="line">    <span class="comment">// 回溯过程中的路径</span></span><br><span class="line">    <span class="keyword">let</span> track = <span class="string">&quot;&quot;</span>;</span><br><span class="line">    <span class="comment">// 可用的左括号和右括号数量初始化为 n</span></span><br><span class="line">    trackback(n, n, track, res);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">trackback</span> (<span class="params">left, right, track, res</span>)</span>&#123;</span><br><span class="line">    <span class="comment">// 若左括号剩下的多，说明不合法</span></span><br><span class="line">    <span class="keyword">if</span> (right &lt; left) <span class="keyword">return</span>;</span><br><span class="line">    <span class="comment">// 数量小于 0 肯定是不合法的</span></span><br><span class="line">    <span class="keyword">if</span> (left &lt; <span class="number">0</span> || right &lt; <span class="number">0</span>) <span class="keyword">return</span>;</span><br><span class="line">    <span class="comment">// 当所有括号都恰好用完时，得到一个合法的括号组合</span></span><br><span class="line">    <span class="keyword">if</span> (left === <span class="number">0</span> &amp;&amp; right === <span class="number">0</span>)&#123;</span><br><span class="line">        res.push(track);</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">   <span class="comment">// 尝试放一个左括号</span></span><br><span class="line">   <span class="comment">// 选择</span></span><br><span class="line">    trackback(left - <span class="number">1</span>, right, track + <span class="string">&#x27;(&#x27;</span>, res);</span><br><span class="line">    <span class="comment">// 撤消选择</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">// 尝试放一个右括号</span></span><br><span class="line">    <span class="comment">// 选择</span></span><br><span class="line">    trackback(left, right - <span class="number">1</span>, track + <span class="string">&#x27;)&#x27;</span>, res);</span><br><span class="line">    <span class="comment">// 撤消选择</span></span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="39-组合总和"><a href="#39-组合总和" class="headerlink" title="39. 组合总和"></a>39. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/combination-sum/">组合总和</a></h4><p>给定一个<strong>无重复元素</strong>的数组 <code>candidates</code> 和一个目标数 <code>target</code> ，找出 <code>candidates</code> 中所有可以使数字和为 <code>target</code> 的组合。</p>
<p><code>candidates</code> 中的数字可以无限制重复被选取。</p>
<p><strong>说明：</strong></p>
<ul>
<li>所有数字（包括 <code>target</code>）都是正整数。</li>
<li>解集不能包含重复的组合。 </li>
</ul>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">输入：candidates &#x3D; [2,3,6,7], target &#x3D; 7,</span><br><span class="line">所求解集为：</span><br><span class="line">[</span><br><span class="line">  [7],</span><br><span class="line">  [2,2,3]</span><br><span class="line">]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">输入：candidates &#x3D; [2,3,5], target &#x3D; 8,</span><br><span class="line">所求解集为：</span><br><span class="line">[</span><br><span class="line">  [2,2,2,2],</span><br><span class="line">  [2,3,3],</span><br><span class="line">  [3,5]</span><br><span class="line">]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= candidates.length &lt;= 30</code></li>
<li><code>1 &lt;= candidates[i] &lt;= 200</code></li>
<li><code>candidate</code> 中的每个元素都是独一无二的。</li>
<li><code>1 &lt;= target &lt;= 500</code></li>
</ul>
<p>保留完成的路径，需要剪枝优化路径</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">candidates</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">target</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[][]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> combinationSum = <span class="function"><span class="keyword">function</span>(<span class="params">candidates, target</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> res = [], cur = [];</span><br><span class="line">    <span class="comment">// 从小到大排序，方便剪枝</span></span><br><span class="line">    candidates.sort(<span class="function">(<span class="params">a, b</span>) =&gt;</span> a - b);</span><br><span class="line">    dfs(target, <span class="number">0</span>);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">    <span class="comment">// residue，剩下的树，begin开始的位置</span></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">dfs</span>(<span class="params">residue, begin</span>)</span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(residue === <span class="number">0</span>)&#123;</span><br><span class="line">            res.push([...cur]);</span><br><span class="line">            <span class="keyword">return</span> ;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">let</span> i = begin; i &lt; candidates.length; i++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(residue - candidates[i] &lt; <span class="number">0</span>)&#123;</span><br><span class="line">                <span class="keyword">return</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 加入当前的树</span></span><br><span class="line">            cur.push(candidates[i]);</span><br><span class="line">            <span class="comment">// DFS</span></span><br><span class="line">            dfs(residue - candidates[i], i);</span><br><span class="line">            <span class="comment">// 撤回</span></span><br><span class="line">            cur.pop();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>写得完整一些</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">candidates</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">target</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[][]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> combinationSum = <span class="function"><span class="keyword">function</span>(<span class="params">candidates, target</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> res = [];</span><br><span class="line">    <span class="keyword">let</span> len = candidates.length;</span><br><span class="line">    candidates.sort(<span class="function">(<span class="params">a, b</span>) =&gt;</span> a - b);</span><br><span class="line">    dfs(candidates, len, target, <span class="number">0</span>, [], res);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br><span class="line"> <span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param </span>candidates 数组输入</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param </span>len        输入数组的长度，冗余变量</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param </span>residue    剩余数值</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param </span>begin      本轮搜索的起点下标</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param </span>path       从根结点到任意结点的路径</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param </span>res        结果集变量</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">dfs</span>(<span class="params">candidates, len, residue, begin, path, res</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (residue == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="comment">// 由于 path 全局只使用一份，到叶子结点的时候需要做一个拷贝</span></span><br><span class="line">        res.push([...path]);</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = begin; i &lt; len; i++) &#123;</span><br><span class="line">        <span class="comment">// 在数组有序的前提下，剪枝</span></span><br><span class="line">        <span class="keyword">if</span> (residue &lt; candidates[i]) <span class="keyword">break</span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 回溯</span></span><br><span class="line">        path.push(candidates[i]);</span><br><span class="line">        dfs(candidates, len, residue - candidates[i], i, path, res);</span><br><span class="line">        path.pop();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="46-全排列"><a href="#46-全排列" class="headerlink" title="46. 全排列"></a>46. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/permutations/">全排列</a></h4><p>给定一个 <strong>没有重复</strong> 数字的序列，返回其所有可能的全排列。</p>
<p><strong>示例:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">输入: [1,2,3]</span><br><span class="line">输出:</span><br><span class="line">[</span><br><span class="line">  [1,2,3],</span><br><span class="line">  [1,3,2],</span><br><span class="line">  [2,1,3],</span><br><span class="line">  [2,3,1],</span><br><span class="line">  [3,1,2],</span><br><span class="line">  [3,2,1]</span><br><span class="line">]</span><br></pre></td></tr></table></figure>

<p>直接用track记录路径</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">nums</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[][]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="comment">/* 主函数，输入一组不重复的数字，返回它们的全排列 */</span></span><br><span class="line"><span class="keyword">var</span> permute = <span class="function"><span class="keyword">function</span>(<span class="params">nums</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> res = [];</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 记录「路径」</span></span><br><span class="line">    <span class="keyword">const</span> track = [];</span><br><span class="line">    <span class="keyword">const</span> n = nums.length;</span><br><span class="line">    <span class="keyword">const</span> isVisited = <span class="keyword">new</span> <span class="built_in">Array</span>(n).fill(<span class="literal">false</span>);</span><br><span class="line">    backtrack(nums, track);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 路径：记录在 track 中</span></span><br><span class="line">    <span class="comment">// 选择列表：nums 中不存在于 track 的那些元素</span></span><br><span class="line">    <span class="comment">// 结束条件：nums 中的元素全都在 track 中出现</span></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">backtrack</span> (<span class="params">nums, track</span>)</span>&#123;</span><br><span class="line">        <span class="comment">// 触发结束条件</span></span><br><span class="line">        <span class="keyword">if</span> (track.length === n)&#123;</span><br><span class="line">            res.push([...track]);</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; n; i++)&#123;</span><br><span class="line">            <span class="comment">// 排除不合法的选择</span></span><br><span class="line">            <span class="keyword">if</span> (!isVisited[i])&#123;</span><br><span class="line">                <span class="comment">// 做选择</span></span><br><span class="line">                isVisited[i] = <span class="literal">true</span>;</span><br><span class="line">                track.push(nums[i]);</span><br><span class="line">                <span class="comment">// 进入下一层决策树</span></span><br><span class="line">                backtrack(nums, track);</span><br><span class="line">                <span class="comment">// 取消选择</span></span><br><span class="line">                isVisited[i] = <span class="literal">false</span>;</span><br><span class="line">                track.pop();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="47-全排列-II"><a href="#47-全排列-II" class="headerlink" title="47. 全排列 II"></a>47. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/permutations-ii/">全排列 II</a></h4><p>给定一个可包含重复数字的序列 <code>nums</code> ，<strong>按任意顺序</strong> 返回所有不重复的全排列。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [1,1,2]</span><br><span class="line">输出：</span><br><span class="line">[[1,1,2],</span><br><span class="line"> [1,2,1],</span><br><span class="line"> [2,1,1]]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [1,2,3]</span><br><span class="line">输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= nums.length &lt;= 8</code></li>
<li><code>-10 &lt;= nums[i] &lt;= 10</code></li>
</ul>
<p>注意通过排序和跳过相同的数进行剪枝</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">nums</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[][]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> permuteUnique = <span class="function"><span class="keyword">function</span>(<span class="params">nums</span>) </span>&#123;</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 回溯法</span></span><br><span class="line"><span class="comment">     * backtrack 解题题公式</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">const</span> res = [];</span><br><span class="line">    <span class="keyword">const</span> len = nums.length;</span><br><span class="line">    <span class="keyword">const</span> used = <span class="keyword">new</span> <span class="built_in">Array</span>(len);</span><br><span class="line">    <span class="comment">// 升序排序</span></span><br><span class="line">    nums.sort(<span class="function">(<span class="params">a, b</span>) =&gt;</span> a - b);</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">dfs</span> (<span class="params">path</span>) </span>&#123;</span><br><span class="line">        <span class="comment">// 个数选够了</span></span><br><span class="line">        <span class="keyword">if</span> (path.length === len) &#123;</span><br><span class="line">            <span class="comment">// path的拷贝 加入解集</span></span><br><span class="line">            res.push([...path]);</span><br><span class="line">            <span class="comment">// 结束当前递归 结束当前分支</span></span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 枚举出所有的选择</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; len; i++) &#123;</span><br><span class="line">            <span class="comment">// 避免产生重复的排列</span></span><br><span class="line">            <span class="keyword">if</span> (nums[i - <span class="number">1</span>] === nums[i] &amp;&amp; i - <span class="number">1</span> &gt;= <span class="number">0</span> &amp;&amp; !used[i - <span class="number">1</span>]) <span class="keyword">continue</span>;</span><br><span class="line">            <span class="comment">// 这个数使用过了，跳过。</span></span><br><span class="line">            <span class="keyword">if</span> (used[i]) <span class="keyword">continue</span>;</span><br><span class="line">            <span class="comment">// make a choice</span></span><br><span class="line">            path.push(nums[i]);</span><br><span class="line">            <span class="comment">// 记录路径上做过的选择</span></span><br><span class="line">            used[i] = <span class="literal">true</span>;</span><br><span class="line">            <span class="comment">// explore，基于它继续选，递归</span></span><br><span class="line">            dfs(path);</span><br><span class="line">            <span class="comment">// undo the choice</span></span><br><span class="line">            path.pop();</span><br><span class="line">            <span class="comment">// 也要撤销一下对它的记录</span></span><br><span class="line">            used[i] = <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;;</span><br><span class="line"></span><br><span class="line">    dfs([]);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="51-N-皇后"><a href="#51-N-皇后" class="headerlink" title="51. N 皇后"></a>51. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/n-queens/">N 皇后</a></h4><p><strong>n 皇后问题</strong> 研究的是如何将 <code>n</code> 个皇后放置在 <code>n×n</code> 的棋盘上，并且使皇后彼此之间不能相互攻击。</p>
<p>给你一个整数 <code>n</code> ，返回所有不同的 <strong>n 皇后问题</strong> 的解决方案。</p>
<p>每一种解法包含一个不同的 <strong>n 皇后问题</strong> 的棋子放置方案，该方案中 <code>&#39;Q&#39;</code> 和 <code>&#39;.&#39;</code> 分别代表了皇后和空位。</p>
<p><strong>示例 1：</strong></p>
<p><img data-src="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210419095805.jpeg" alt="img"></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 4</span><br><span class="line">输出：[[&quot;.Q..&quot;,&quot;...Q&quot;,&quot;Q...&quot;,&quot;..Q.&quot;],[&quot;..Q.&quot;,&quot;Q...&quot;,&quot;...Q&quot;,&quot;.Q..&quot;]]</span><br><span class="line">解释：如上图所示，4 皇后问题存在两个不同的解法。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 1</span><br><span class="line">输出：[[&quot;Q&quot;]]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= n &lt;= 9</code></li>
<li>皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。</li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">n</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;string[][]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> solveNQueens = <span class="function"><span class="keyword">function</span>(<span class="params">n</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> res = [];</span><br><span class="line">    backtrack(n, []);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">backtrack</span>(<span class="params">n, tmp</span>) </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (tmp.length === n) &#123;</span><br><span class="line">            <span class="keyword">let</span> arr = [];</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">                arr[i] = <span class="string">&quot;.&quot;</span>.repeat(tmp[i]) + <span class="string">&quot;Q&quot;</span> + <span class="string">&quot;.&quot;</span>.repeat(n - tmp[i] - <span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">            res.push(arr);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (isValid(tmp, j)) &#123;</span><br><span class="line">                tmp.push(j);</span><br><span class="line">                backtrack(n, tmp);</span><br><span class="line">                tmp.pop();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">isValid</span>(<span class="params">arr, j</span>) </span>&#123;</span><br><span class="line">        <span class="keyword">let</span> i = arr.length;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> x = <span class="number">0</span>; x &lt; i; x++) &#123;</span><br><span class="line">            <span class="keyword">let</span> y = arr[x];</span><br><span class="line">            <span class="keyword">if</span>  (y === j || x + y === i + j || x - y === i - j) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>回溯</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> solveNQueens = <span class="function"><span class="keyword">function</span>(<span class="params">n</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> res = [];</span><br><span class="line">    dfs([], <span class="number">0</span>);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">    <span class="comment">// 递归调用，初始为空数组（每行皇后的列位置），从第0行开始</span></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">dfs</span> (<span class="params">subRes, row</span>) </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(row === n) &#123;</span><br><span class="line">            <span class="comment">// 将每行展开为..Q..形式</span></span><br><span class="line">            <span class="keyword">return</span> res.push(subRes.map(<span class="function"><span class="params">i</span> =&gt;</span> <span class="string">&#x27;.&#x27;</span>.repeat(i) + <span class="string">&#x27;Q&#x27;</span> + <span class="string">&#x27;.&#x27;</span>.repeat(n - i -<span class="number">1</span>)));</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 遍历每一列，使得目前行数的皇后在第col列 </span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> col = <span class="number">0</span>; col &lt; n; col++ ) &#123;</span><br><span class="line">            <span class="comment">// 遍历数组使得皇后不互相攻击</span></span><br><span class="line">            <span class="keyword">if</span>(!subRes.some(<span class="function">(<span class="params">j, k</span>) =&gt;</span> (j === col || <span class="built_in">Math</span>.abs(j - col) === <span class="built_in">Math</span>.abs(k - row)))) &#123;</span><br><span class="line">                <span class="comment">// 执行操作</span></span><br><span class="line">                subRes.push(col);</span><br><span class="line">                <span class="comment">// 回溯</span></span><br><span class="line">                dfs(subRes, row + <span class="number">1</span>);</span><br><span class="line">                <span class="comment">// 撤回</span></span><br><span class="line">                subRes.pop();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="52-N皇后-II"><a href="#52-N皇后-II" class="headerlink" title="52. N皇后 II"></a>52. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/n-queens-ii/">N皇后 II</a></h4><p><strong>n 皇后问题</strong> 研究的是如何将 <code>n</code> 个皇后放置在 <code>n×n</code> 的棋盘上，并且使皇后彼此之间不能相互攻击。</p>
<p>给你一个整数 <code>n</code> ，返回 <strong>n 皇后问题</strong> 不同的解决方案的数量。</p>
<p><strong>示例 1：</strong></p>
<p><img data-src="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210419095744.jpeg" alt="img"></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 4</span><br><span class="line">输出：2</span><br><span class="line">解释：如上图所示，4 皇后问题存在两个不同的解法。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 1</span><br><span class="line">输出：1</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= n &lt;= 9</code></li>
<li>皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。</li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">n</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> totalNQueens = <span class="function"><span class="keyword">function</span>(<span class="params">n</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> res = <span class="number">0</span>;</span><br><span class="line">    backtrack(n, []);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">backtrack</span>(<span class="params">n, tmp</span>) </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (tmp.length === n) &#123;</span><br><span class="line">            <span class="comment">// 已回溯到最后一行，找到一种方案</span></span><br><span class="line">            res++;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 尝试当前行放入第j列</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</span><br><span class="line">            <span class="comment">// 如果可行，放入当前列</span></span><br><span class="line">            <span class="keyword">if</span> (isValid(tmp, j)) &#123;</span><br><span class="line">                <span class="comment">// 记录当前选择</span></span><br><span class="line">                tmp.push(j);</span><br><span class="line">                <span class="comment">// 继续下一次递归</span></span><br><span class="line">                backtrack(n, tmp);</span><br><span class="line">                <span class="comment">// 撤销当前选择</span></span><br><span class="line">                tmp.pop();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 判断当前列是否有效</span></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">isValid</span>(<span class="params">arr, col</span>) </span>&#123;</span><br><span class="line">        <span class="keyword">let</span> len = arr.length;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> x = <span class="number">0</span>; x &lt; len; x++) &#123;</span><br><span class="line">            <span class="keyword">let</span> y = arr[x];</span><br><span class="line">            <span class="keyword">if</span> (y === col || x - y === len - col || x + y === col + len) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="78-子集"><a href="#78-子集" class="headerlink" title="78. 子集"></a>78. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/subsets/">子集</a></h4><p>给你一个整数数组 <code>nums</code> ，数组中的元素 <strong>互不相同</strong> 。返回该数组所有可能的子集（幂集）。</p>
<p>解集 <strong>不能</strong> 包含重复的子集。你可以按 <strong>任意顺序</strong> 返回解集。 </p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [1,2,3]</span><br><span class="line">输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [0]</span><br><span class="line">输出：[[],[0]]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= nums.length &lt;= 10</code></li>
<li><code>-10 &lt;= nums[i] &lt;= 10</code></li>
<li><code>nums</code> 中的所有元素 <strong>互不相同</strong></li>
</ul>
<p>回溯法，遍历各种可行方法，路径重复剪枝</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">nums</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[][]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="comment">// 数学归纳法</span></span><br><span class="line"><span class="keyword">var</span> subsets = <span class="function"><span class="keyword">function</span>(<span class="params">nums</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> res = [];</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 记录「路径」</span></span><br><span class="line">    <span class="keyword">const</span> track = [];</span><br><span class="line">    backtrack(nums, <span class="number">0</span>, track);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">backtrack</span> (<span class="params">nums, start, track</span>)</span>&#123;</span><br><span class="line">        res.push(track);</span><br><span class="line">        </span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> i = start; i &lt; nums.length; i++)&#123;</span><br><span class="line">            <span class="comment">// 排除不合法的选择</span></span><br><span class="line">            <span class="keyword">if</span> (!track.includes(nums[i]))&#123;</span><br><span class="line">                <span class="comment">// 做选择</span></span><br><span class="line">                track.push(nums[i]);</span><br><span class="line">                <span class="comment">// 进入下一层决策树</span></span><br><span class="line">                backtrack(nums, i + <span class="number">1</span>, [...track]);</span><br><span class="line">                <span class="comment">// 取消选择</span></span><br><span class="line">                track.pop();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>数学归纳法</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">nums</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[][]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="comment">// 数学归纳法</span></span><br><span class="line"><span class="keyword">var</span> subsets = <span class="function"><span class="keyword">function</span>(<span class="params">nums</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// base case，返回一个空集</span></span><br><span class="line">    <span class="keyword">if</span> (nums.length === <span class="number">0</span>) <span class="keyword">return</span> [[]];</span><br><span class="line">    <span class="keyword">let</span> n = nums.pop();</span><br><span class="line">    <span class="comment">// 先递归算出前面元素的所有子集</span></span><br><span class="line">    <span class="keyword">let</span> res = subsets(nums);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">let</span> len = res.length;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; len; i++) &#123;</span><br><span class="line">        <span class="comment">// 然后在之前的结果之上追加</span></span><br><span class="line">        res.push([...res[i], n]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>将上述数学归纳法中的递归改为回溯</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">nums</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[][]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="comment">// 数学归纳法</span></span><br><span class="line"><span class="keyword">var</span> subsets = <span class="function"><span class="keyword">function</span>(<span class="params">nums</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> res = [[]];</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; nums.length; i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">let</span> j = <span class="number">0</span>, len = res.length; j &lt; len; j++)&#123;</span><br><span class="line">            res.push(res[j].concat(nums[i]));</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="79-单词搜索"><a href="#79-单词搜索" class="headerlink" title="79. 单词搜索"></a>79. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/word-search/">单词搜索</a></h4><p>给定一个 <code>m x n</code> 二维字符网格 <code>board</code> 和一个字符串单词 <code>word</code> 。如果 <code>word</code> 存在于网格中，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>
<p>单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。</p>
<p><strong>示例 1：</strong></p>
<p><img data-src="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210711174412.jpeg" alt="img"></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：board &#x3D; [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word &#x3D; &quot;ABCCED&quot;</span><br><span class="line">输出：true</span><br></pre></td></tr></table></figure>

<p>示例 2：</p>
<p><img data-src="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210711174506.jpeg" alt="img"></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：board &#x3D; [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word &#x3D; &quot;SEE&quot;</span><br><span class="line">输出：true</span><br></pre></td></tr></table></figure>

<p>示例 3：</p>
<p><img data-src="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210711174617.jpeg" alt="img"></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：board &#x3D; [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word &#x3D; &quot;ABCB&quot;</span><br><span class="line">输出：false</span><br></pre></td></tr></table></figure>


<p>提示：</p>
<p>m == board.length<br>n = board[i].length<br>1 &lt;= m, n &lt;= 6<br>1 &lt;= word.length &lt;= 15<br>board 和 word 仅由大小写英文字母组成</p>
<p>进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;character[][]&#125;</span> <span class="variable">board</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string&#125;</span> <span class="variable">word</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> exist = <span class="function"><span class="keyword">function</span>(<span class="params">board, word</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (board.length === <span class="number">0</span> || board[<span class="number">0</span>].length === <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    <span class="keyword">if</span> (word.length === <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">let</span> row = board.length;</span><br><span class="line">    <span class="keyword">let</span> col = board[<span class="number">0</span>].length;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; row; i ++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; col; j++) &#123;</span><br><span class="line">            <span class="comment">// 存在一个序列即返回true</span></span><br><span class="line">            <span class="keyword">if</span> (backtrack(i, j, <span class="number">0</span>)) <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    <span class="comment">// 行，列，当前索引</span></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">backtrack</span>(<span class="params">i, j, index</span>) </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(i &gt;= row || i &lt; <span class="number">0</span> || j &gt;= col || j &lt; <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">const</span> cur = board[i][j];</span><br><span class="line">        <span class="keyword">if</span> (cur !== word[index]) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">if</span> (index === word.length - <span class="number">1</span>) <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        <span class="comment">// 该位置的数对应单次的当前索引</span></span><br><span class="line">        <span class="comment">// 修改当前节点状态</span></span><br><span class="line">        board[i][j] = <span class="number">0</span>;</span><br><span class="line">        <span class="comment">// 利用短路效应剪枝回溯</span></span><br><span class="line">        <span class="keyword">const</span> res = backtrack(i + <span class="number">1</span>, j, index + <span class="number">1</span>) || backtrack(i - <span class="number">1</span>, j, index + <span class="number">1</span>) || backtrack(i, j + <span class="number">1</span>, index + <span class="number">1</span>) || backtrack(i, j - <span class="number">1</span>, index + <span class="number">1</span>);</span><br><span class="line">        <span class="comment">// 回改当前节点状态</span></span><br><span class="line">        board[i][j] = cur;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>当然也可以用额外的空间存储</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;character[][]&#125;</span> <span class="variable">board</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string&#125;</span> <span class="variable">word</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> exist = <span class="function"><span class="keyword">function</span>(<span class="params">board, word</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> m = board.length;</span><br><span class="line">    <span class="keyword">const</span> n = board[<span class="number">0</span>].length;</span><br><span class="line">    <span class="comment">// 二维矩阵used</span></span><br><span class="line">    <span class="keyword">const</span> used = <span class="keyword">new</span> <span class="built_in">Array</span>(m);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</span><br><span class="line">        used[i] = <span class="keyword">new</span> <span class="built_in">Array</span>(n);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 判断当前点是否是目标路径上的点</span></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">canFind</span> (<span class="params">row, col, i</span>) </span>&#123;</span><br><span class="line">        <span class="comment">// row col是当前点的坐标，i是当前考察的字符索引</span></span><br><span class="line">        <span class="comment">// 递归的出口</span></span><br><span class="line">        <span class="keyword">if</span> (i &gt; word.length - <span class="number">1</span>) &#123;  </span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 当前点要存在</span></span><br><span class="line">        <span class="keyword">if</span> (row &lt; <span class="number">0</span> || row &gt;= m || col &lt; <span class="number">0</span> || col &gt;= n) &#123; </span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 当前的点已经走过，或当前点就不是目标点</span></span><br><span class="line">        <span class="keyword">if</span> (used[row][col] || board[row][col] != word[i]) &#123; </span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 排除掉这些false情况，当前点是没问题的，可以继续递归考察</span></span><br><span class="line">        <span class="comment">// used记录一下当前点被访问了</span></span><br><span class="line">        used[row][col] = <span class="literal">true</span>; </span><br><span class="line">        <span class="keyword">const</span> canFindRest =</span><br><span class="line">            canFind(row + <span class="number">1</span>, col, i + <span class="number">1</span>) ||</span><br><span class="line">            canFind(row - <span class="number">1</span>, col, i + <span class="number">1</span>) ||</span><br><span class="line">            canFind(row, col + <span class="number">1</span>, i + <span class="number">1</span>) ||</span><br><span class="line">            canFind(row, col - <span class="number">1</span>, i + <span class="number">1</span>); </span><br><span class="line">        <span class="comment">// 基于当前点，可以为剩下的字符找到路径</span></span><br><span class="line">        <span class="keyword">if</span> (canFindRest) &#123; </span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;    </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 找不出，返回false，继续考察别的分支，并撤销当前点的访问状态。</span></span><br><span class="line">        used[row][col] = <span class="literal">false</span>; </span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</span><br><span class="line">            <span class="comment">// 找到dfs的起点</span></span><br><span class="line">            <span class="keyword">if</span> (board[i][j] == word[<span class="number">0</span>] &amp;&amp; canFind(i, j, <span class="number">0</span>)) &#123;</span><br><span class="line">                <span class="comment">// 找到起点，且dfs的结果也true，则找到了目标路径</span></span><br><span class="line">                <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 怎么样都没有返回true，则返回false</span></span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="200-岛屿数量"><a href="#200-岛屿数量" class="headerlink" title="200. 岛屿数量"></a>200. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/number-of-islands/">岛屿数量</a></h4><p>给你一个由 <code>&#39;1&#39;</code>（陆地）和 <code>&#39;0&#39;</code>（水）组成的的二维网格，请你计算网格中岛屿的数量。</p>
<p>岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。</p>
<p>此外，你可以假设该网格的四条边均被水包围。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">输入：grid &#x3D; [</span><br><span class="line">  [&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;0&quot;],</span><br><span class="line">  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;],</span><br><span class="line">  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],</span><br><span class="line">  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;]</span><br><span class="line">]</span><br><span class="line">输出：1</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">输入：grid &#x3D; [</span><br><span class="line">  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],</span><br><span class="line">  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],</span><br><span class="line">  [&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],</span><br><span class="line">  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;]</span><br><span class="line">]</span><br><span class="line">输出：3</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>m == grid.length</code></li>
<li><code>n == grid[i].length</code></li>
<li><code>1 &lt;= m, n &lt;= 300</code></li>
<li><code>grid[i][j]</code> 的值为 <code>&#39;0&#39;</code> 或 <code>&#39;1&#39;</code></li>
</ul>
<p>DFS深度优先</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;character[][]&#125;</span> <span class="variable">grid</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> numIslands = <span class="function"><span class="keyword">function</span>(<span class="params">grid</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> row = grid.length;</span><br><span class="line">    <span class="keyword">if</span>(!row) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">let</span> col = grid[<span class="number">0</span>].length;</span><br><span class="line">    <span class="keyword">let</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// DFS，将连在一起的几个 ‘1’全部转为‘0’</span></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">DFS</span>(<span class="params">grid, r, c</span>)</span>&#123;</span><br><span class="line">        grid[r][c] = <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">        <span class="keyword">if</span>(r - <span class="number">1</span> &gt;= <span class="number">0</span> &amp;&amp; grid[r - <span class="number">1</span>][c] === <span class="string">&#x27;1&#x27;</span>) DFS(grid, r - <span class="number">1</span>, c);</span><br><span class="line">        <span class="keyword">if</span>(r + <span class="number">1</span> &lt; row &amp;&amp; grid[r + <span class="number">1</span>][c] === <span class="string">&#x27;1&#x27;</span>) DFS(grid, r + <span class="number">1</span>, c);</span><br><span class="line">        <span class="keyword">if</span>(c - <span class="number">1</span> &gt;= <span class="number">0</span> &amp;&amp; grid[r][c - <span class="number">1</span>] === <span class="string">&#x27;1&#x27;</span>) DFS(grid, r, c - <span class="number">1</span>);</span><br><span class="line">        <span class="keyword">if</span>(c + <span class="number">1</span> &lt; col &amp;&amp; grid[r][c + <span class="number">1</span>] ===<span class="string">&#x27;1&#x27;</span>) DFS(grid, r, c + <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; row; i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; col; j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(grid[i][j] === <span class="string">&#x27;1&#x27;</span>)&#123;</span><br><span class="line">                res++;</span><br><span class="line">                DFS(grid, i, j);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>BFS广度优先</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;character[][]&#125;</span> <span class="variable">grid</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> numIslands = <span class="function"><span class="keyword">function</span>(<span class="params">grid</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (grid.length === <span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">let</span> lenx = grid.length;</span><br><span class="line">    <span class="keyword">let</span> leny = grid[<span class="number">0</span>].length;</span><br><span class="line">    <span class="keyword">let</span> num_islands = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; lenx; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; leny; j++)&#123;</span><br><span class="line">            <span class="keyword">if</span> (grid[i][j] === <span class="number">1</span>) &#123;</span><br><span class="line">               num_islands++;</span><br><span class="line">               grid[i][j] = <span class="number">0</span>;</span><br><span class="line">               neighbors = <span class="keyword">new</span> <span class="built_in">Array</span>();</span><br><span class="line">               neighbors.push([i, j]);</span><br><span class="line">               <span class="keyword">while</span> (neighbors.length !== <span class="number">0</span>)&#123;</span><br><span class="line">                   <span class="keyword">let</span> x = neighbors[<span class="number">0</span>][<span class="number">0</span>];</span><br><span class="line">                   <span class="keyword">let</span> y = neighbors[<span class="number">0</span>][<span class="number">1</span>];</span><br><span class="line">                   <span class="keyword">if</span> (x - <span class="number">1</span> &gt;= <span class="number">0</span> &amp;&amp; grid[x - <span class="number">1</span>][y] === <span class="number">1</span>) &#123;</span><br><span class="line">                        neighbors.push([x - <span class="number">1</span>, y]);</span><br><span class="line">                        grid[x - <span class="number">1</span>][y] = <span class="number">0</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">if</span> (x + <span class="number">1</span> &lt; lenx &amp;&amp; grid[x + <span class="number">1</span>][y] === <span class="number">1</span>) &#123;</span><br><span class="line">                        neighbors.push([x + <span class="number">1</span>, y]);</span><br><span class="line">                        grid[x + <span class="number">1</span>][y] = <span class="number">0</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">if</span> (y - <span class="number">1</span> &gt;= <span class="number">0</span> &amp;&amp; grid[x][y - <span class="number">1</span>] === <span class="number">1</span>) &#123;</span><br><span class="line">                        neighbors.push([x, y - <span class="number">1</span>]);</span><br><span class="line">                        grid[x][y - <span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">if</span> (y + <span class="number">1</span> &lt; leny &amp;&amp; grid[x][y + <span class="number">1</span>] === <span class="number">1</span>) &#123;</span><br><span class="line">                        neighbors.push([x, y + <span class="number">1</span>]);</span><br><span class="line">                        grid[x][y + <span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    neighbors.shift();</span><br><span class="line">               &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> num_islands;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="207-课程表"><a href="#207-课程表" class="headerlink" title="207. 课程表"></a>207. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/course-schedule/">课程表</a></h4><p>你这个学期必须选修 <code>numCourses</code> 门课程，记为 <code>0</code> 到 <code>numCourses - 1</code> 。</p>
<p>在选修某些课程之前需要一些先修课程。 先修课程按数组 <code>prerequisites</code> 给出，其中 <code>prerequisites[i] = [ai, bi]</code> ，表示如果要学习课程 <code>ai</code> 则 <strong>必须</strong> 先学习课程 <code>bi</code> 。</p>
<ul>
<li>例如，先修课程对 <code>[0, 1]</code> 表示：想要学习课程 <code>0</code> ，你需要先完成课程 <code>1</code> 。</li>
</ul>
<p>请你判断是否可能完成所有课程的学习？如果可以，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>
<p> <strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：numCourses &#x3D; 2, prerequisites &#x3D; [[1,0]]</span><br><span class="line">输出：true</span><br><span class="line">解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：numCourses &#x3D; 2, prerequisites &#x3D; [[1,0],[0,1]]</span><br><span class="line">输出：false</span><br><span class="line">解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。</span><br></pre></td></tr></table></figure>

<p> <strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= numCourses &lt;= 105</code></li>
<li><code>0 &lt;= prerequisites.length &lt;= 5000</code></li>
<li><code>prerequisites[i].length == 2</code></li>
<li><code>0 &lt;= ai, bi &lt; numCourses</code></li>
<li><code>prerequisites[i]</code> 中的所有课程对<strong>互不相同</strong></li>
</ul>
<p>邻接表+BFS</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">numCourses</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[][]&#125;</span> <span class="variable">prerequisites</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> canFinish = <span class="function"><span class="keyword">function</span>(<span class="params">numCourses, prerequisites</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> inDegree = <span class="keyword">new</span> <span class="built_in">Array</span>(numCourses).fill(<span class="number">0</span>);</span><br><span class="line">    <span class="comment">// 邻接表</span></span><br><span class="line">    <span class="keyword">let</span> graph = &#123;&#125;;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; prerequisites.length; i++) &#123;</span><br><span class="line">        <span class="comment">// 计算课对应的入度</span></span><br><span class="line">        inDegree[prerequisites[i][<span class="number">0</span>]]++;</span><br><span class="line">        <span class="comment">// 当前课已经存在于邻接表</span></span><br><span class="line">        <span class="keyword">if</span> (graph[prerequisites[i][<span class="number">1</span>]]) &#123;</span><br><span class="line">            <span class="comment">// 对应的数组新推入依赖它的课</span></span><br><span class="line">            graph[prerequisites[i][<span class="number">1</span>]].push(prerequisites[i][<span class="number">0</span>]);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123; <span class="comment">// 当前课不存在于邻接表</span></span><br><span class="line">            <span class="comment">// 推入依赖它的课</span></span><br><span class="line">            graph[prerequisites[i][<span class="number">1</span>]] = [prerequisites[i][<span class="number">0</span>]];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// BFS需要的队列</span></span><br><span class="line">    <span class="keyword">const</span> queue = [];</span><br><span class="line">    <span class="comment">// 初始推入所有入度0的课</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; inDegree.length; i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (inDegree[i] === <span class="number">0</span>) queue.push(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(queue.length) &#123;</span><br><span class="line">        <span class="comment">// 可选的课，出栈</span></span><br><span class="line">        <span class="keyword">const</span> select = queue.shift();</span><br><span class="line">        <span class="comment">// 获取这门课对应的后续课</span></span><br><span class="line">        <span class="keyword">const</span> toEnQueue = graph[select];</span><br><span class="line">        <span class="comment">// 确实有后续课</span></span><br><span class="line">        <span class="keyword">if</span> (toEnQueue &amp;&amp; toEnQueue.length) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">let</span> i <span class="keyword">in</span> toEnQueue) &#123;</span><br><span class="line">                <span class="comment">// 依赖它的后续课的入度-1</span></span><br><span class="line">                inDegree[toEnQueue[i]]--;</span><br><span class="line">                <span class="comment">// 如果因此减为0，入列</span></span><br><span class="line">                <span class="keyword">if</span> (inDegree[toEnQueue[i]] === <span class="number">0</span>) &#123;</span><br><span class="line">                    <span class="comment">// 这门课入列</span></span><br><span class="line">                    queue.push(toEnQueue[i]);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i <span class="keyword">in</span> inDegree) &#123;</span><br><span class="line">        <span class="comment">// 还有课的入度不为0</span></span><br><span class="line">        <span class="keyword">if</span> (inDegree[i] !== <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;; </span><br></pre></td></tr></table></figure>

<h4 id="301-删除无效的括号"><a href="#301-删除无效的括号" class="headerlink" title="301. 删除无效的括号"></a>301. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/remove-invalid-parentheses/">删除无效的括号</a></h4><p>给你一个由若干括号和字母组成的字符串 <code>s</code> ，删除最小数量的无效括号，使得输入的字符串有效。</p>
<p>返回所有可能的结果。答案可以按 <strong>任意顺序</strong> 返回。</p>
<p> <strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：s &#x3D; &quot;()())()&quot;</span><br><span class="line">输出：[&quot;(())()&quot;,&quot;()()()&quot;]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：s &#x3D; &quot;(a)())()&quot;</span><br><span class="line">输出：[&quot;(a())()&quot;,&quot;(a)()()&quot;]</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：s &#x3D; &quot;)(&quot;</span><br><span class="line">输出：[&quot;&quot;]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= s.length &lt;= 25</code></li>
<li><code>s</code> 由小写英文字母以及括号 <code>&#39;(&#39;</code> 和 <code>&#39;)&#39;</code> 组成</li>
<li><code>s</code> 中至多含 <code>20</code> 个括号</li>
</ul>
<p>回溯法/DFS/暴力<br>需要解决几个关键点。</p>
<p>第一，怎么判断括号是否匹配？</p>
<p>[20 题](<a target="_blank" rel="noopener" href="https://leetcode.wang/leetCode-20-Valid">https://leetcode.wang/leetCode-20-Valid</a> Parentheses.html) 的时候做过括号匹配的问题，除了使用栈，我们也可以用一个计数器 count，遇到左括号进行加 1 ，遇到右括号进行减 1，如果最后计数器是 0，说明括号是匹配的。</p>
<p>第二，如果用暴力的方法，怎么列举所有情况？</p>
<p>要列举所有的情况，每个括号无非是两种状态，在或者不在，字母的话就只有「在」一种情况。我们可以通过回溯法或者说是 DFS 。可以参考下边的图。</p>
<p>对于 (a)())， 如下图，蓝色表示在，橙色表示不在，下边是第一个字符在的情况。</p>
<p><img data-src="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210716080758.jpeg" alt="img"></p>
<p>下边是第一个字符不在的情况。</p>
<p><img data-src="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210716080814.jpeg" alt="img"></p>
<p>我们要做的就是从第一个字符开始，通过深度优先遍历的顺序，遍历到最后一个字符后判断当前路径上的字符串是否合法。</p>
<p>对于代码的话，我们可以一边遍历，一边记录当前 count 的情况，也就是左右括号的情况。到最后一个字符后，只需要判断 count 是否为 0 即可。</p>
<p>第三，怎么保证删掉最少的括号？</p>
<p>这个方法很多，说一下我的。假设我们用 res 数组保存最终的结果，当新的字符串要加入的时候，我们判断一下新加入的字符串的长度和数组中第一个元素长度的关系。</p>
<p>如果新加入的字符串的长度大于数组中第一个元素的长度，我们就清空数组，然后再将新字符串加入。</p>
<p>如果新加入的字符串的长度小于数组中第一个元素的长度，那么当前字符串抛弃掉。</p>
<p>如果新加入的字符串的长度等于数组中第一个元素的长度，将新字符串加入到 res 中。</p>
<p>第四，重复的情况怎么办？</p>
<p>简单粗暴一些，最后通过 set 去重即可。</p>
<p>上边四个问题解决后，就可以写代码了。</p>
<p>因为我们考虑的是删除最少的括号数，我们可以在深度优先遍历之前记录需要删除的左括号的个数和右括号的个数，遍历过程中如果删除的超过了需要删除的括号个数，就可以直接结束。</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string&#125;</span> <span class="variable">s</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;string[]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> removeInvalidParentheses = <span class="function"><span class="keyword">function</span> (<span class="params">s</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> res = [<span class="string">&#x27;&#x27;</span>];</span><br><span class="line">    removeInvalidParenthesesHelper(s, <span class="number">0</span>, s.length, <span class="number">0</span>, <span class="string">&#x27;&#x27;</span>, res);</span><br><span class="line">    <span class="comment">// 去重</span></span><br><span class="line">    <span class="keyword">return</span> [...new <span class="built_in">Set</span>(res)];</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * </span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string 原字符串&#125;</span> </span>s </span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number 当前考虑的字符下标&#125;</span> </span>start </span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number s 的长度&#125;</span> </span>end </span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number 记录左括号和右括号的情况&#125;</span> </span>count </span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string 遍历的路径字符串&#125;</span> </span>temp </span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string[] 保存最终的结果&#125;</span> </span>res </span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">removeInvalidParenthesesHelper</span>(<span class="params">s, start, end, count, temp, res</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 当前右括号多了, 后边无论是什么都不可能是合法字符串了, 直接结束</span></span><br><span class="line">    <span class="keyword">if</span> (count &lt; <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 到达结尾</span></span><br><span class="line">    <span class="keyword">if</span> (start === end) &#123;</span><br><span class="line">        <span class="keyword">if</span> (count === <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">let</span> max = res[<span class="number">0</span>].length;</span><br><span class="line">            <span class="keyword">if</span> (temp.length &gt; max) &#123;</span><br><span class="line">                <span class="comment">// 清空之前的</span></span><br><span class="line">                res.length = <span class="number">0</span>;</span><br><span class="line">                <span class="comment">// 将当前的加入</span></span><br><span class="line">                res.push(temp);</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (temp.length === max) &#123;</span><br><span class="line">                res.push(temp);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 添加当前字符</span></span><br><span class="line">    <span class="keyword">if</span> (s[start] === <span class="string">&#x27;(&#x27;</span>) &#123;</span><br><span class="line">        removeInvalidParenthesesHelper(</span><br><span class="line">            s,</span><br><span class="line">            start + <span class="number">1</span>,</span><br><span class="line">            end,</span><br><span class="line">            count + <span class="number">1</span>,</span><br><span class="line">            temp + <span class="string">&#x27;(&#x27;</span>,</span><br><span class="line">            res</span><br><span class="line">        );</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (s[start] === <span class="string">&#x27;)&#x27;</span>) &#123;</span><br><span class="line">        removeInvalidParenthesesHelper(</span><br><span class="line">            s,</span><br><span class="line">            start + <span class="number">1</span>,</span><br><span class="line">            end,</span><br><span class="line">            count - <span class="number">1</span>,</span><br><span class="line">            temp + <span class="string">&#x27;)&#x27;</span>,</span><br><span class="line">            res</span><br><span class="line">        );</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        removeInvalidParenthesesHelper(</span><br><span class="line">            s,</span><br><span class="line">            start + <span class="number">1</span>,</span><br><span class="line">            end,</span><br><span class="line">            count,</span><br><span class="line">            temp + s.charAt(start),</span><br><span class="line">            res</span><br><span class="line">        );</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 不添加当前字符</span></span><br><span class="line">    <span class="keyword">if</span> (s[start] === <span class="string">&#x27;(&#x27;</span> || s[start] === <span class="string">&#x27;)&#x27;</span>) &#123;</span><br><span class="line">        removeInvalidParenthesesHelper(s, start + <span class="number">1</span>, end, count, temp, res);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>BFS</p>
<p>思想很简单，先判断整个字符串是否合法， 如果合法的话就将其加入到结果中。否则的话，进行下一步。</p>
<p>只删掉 1 个括号，考虑所有的删除情况，然后判断剩下的字符串是否合法，如果合法的话就将其加入到结果中。否则的话，进行下一步。</p>
<p>只删掉 2 个括号，考虑所有的删除情况，然后判断剩下的字符串是否合法，如果合法的话就将其加入到结果中。否则的话，进行下一步。</p>
<p>只删掉 3 个括号，考虑所有的删除情况，然后判断剩下的字符串是否合法，如果合法的话就将其加入到结果中。否则的话，进行下一步。</p>
<p>…</p>
<p>因为我们考虑删除最少的括号数，如果上边某一步出现了合法情况，后边的步骤就不用进行了。</p>
<p>同样要解决重复的问题，除了解法一在最后返回前用 set 去重。这里我们也可以在过程中使用一个 set ，在加入队列之前判断一下是否重复。</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string&#125;</span> <span class="variable">s</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;string[]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> removeInvalidParentheses = <span class="function"><span class="keyword">function</span> (<span class="params">s</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> res = [];</span><br><span class="line">    <span class="keyword">let</span> queue = [];</span><br><span class="line"></span><br><span class="line">    queue.push([s, <span class="number">0</span>]);</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">while</span> (queue.length &gt; <span class="number">0</span>) &#123;</span><br><span class="line">        s = queue.shift();</span><br><span class="line">        <span class="keyword">if</span> (isVaild(s[<span class="number">0</span>])) &#123;</span><br><span class="line">            res.push(s[<span class="number">0</span>]);</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (res.length === <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">let</span> removei = s[<span class="number">1</span>];</span><br><span class="line">            s = s[<span class="number">0</span>];</span><br><span class="line">            <span class="keyword">for</span> (; removei &lt; s.length; removei++) &#123;</span><br><span class="line">                <span class="keyword">if</span> (</span><br><span class="line">                    <span class="comment">// 保证是连续括号的第一个</span></span><br><span class="line">                    (s[removei] === <span class="string">&#x27;(&#x27;</span> || s[removei] === <span class="string">&#x27;)&#x27;</span>) &amp;&amp;</span><br><span class="line">                    (removei === <span class="number">0</span> || s[removei - <span class="number">1</span>] != s[removei])</span><br><span class="line">                ) &#123;</span><br><span class="line">                    <span class="keyword">let</span> nexts = s.substring(<span class="number">0</span>, removei) + s.substring(removei + <span class="number">1</span>);</span><br><span class="line">                    <span class="comment">// 此时删除位置的下标 removei 就是下次删除位置的开始</span></span><br><span class="line">                    queue.push([nexts, removei]);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">isVaild</span>(<span class="params">s</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> count = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; s.length; i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (s[i] === <span class="string">&#x27;(&#x27;</span>) &#123;</span><br><span class="line">            count++;</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (s[i] === <span class="string">&#x27;)&#x27;</span>) &#123;</span><br><span class="line">            count--;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (count &lt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> count === <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="399-除法求值"><a href="#399-除法求值" class="headerlink" title="399. 除法求值"></a>399. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/evaluate-division/">除法求值</a></h4><p>给你一个变量对数组 <code>equations</code> 和一个实数值数组 <code>values</code> 作为已知条件，其中 <code>equations[i] = [Ai, Bi]</code> 和 <code>values[i]</code> 共同表示等式 <code>Ai / Bi = values[i]</code> 。每个 <code>Ai</code> 或 <code>Bi</code> 是一个表示单个变量的字符串。</p>
<p>另有一些以数组 <code>queries</code> 表示的问题，其中 <code>queries[j] = [Cj, Dj]</code> 表示第 <code>j</code> 个问题，请你根据已知条件找出 <code>Cj / Dj = ?</code> 的结果作为答案。</p>
<p>返回 <strong>所有问题的答案</strong> 。如果存在某个无法确定的答案，则用 <code>-1.0</code> 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 <code>-1.0</code> 替代这个答案。</p>
<p><strong>注意：</strong>输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">输入：equations &#x3D; [[&quot;a&quot;,&quot;b&quot;],[&quot;b&quot;,&quot;c&quot;]], values &#x3D; [2.0,3.0], queries &#x3D; [[&quot;a&quot;,&quot;c&quot;],[&quot;b&quot;,&quot;a&quot;],[&quot;a&quot;,&quot;e&quot;],[&quot;a&quot;,&quot;a&quot;],[&quot;x&quot;,&quot;x&quot;]]</span><br><span class="line">输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]</span><br><span class="line">解释：</span><br><span class="line">条件：a &#x2F; b &#x3D; 2.0, b &#x2F; c &#x3D; 3.0</span><br><span class="line">问题：a &#x2F; c &#x3D; ?, b &#x2F; a &#x3D; ?, a &#x2F; e &#x3D; ?, a &#x2F; a &#x3D; ?, x &#x2F; x &#x3D; ?</span><br><span class="line">结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：equations &#x3D; [[&quot;a&quot;,&quot;b&quot;],[&quot;b&quot;,&quot;c&quot;],[&quot;bc&quot;,&quot;cd&quot;]], values &#x3D; [1.5,2.5,5.0], queries &#x3D; [[&quot;a&quot;,&quot;c&quot;],[&quot;c&quot;,&quot;b&quot;],[&quot;bc&quot;,&quot;cd&quot;],[&quot;cd&quot;,&quot;bc&quot;]]</span><br><span class="line">输出：[3.75000,0.40000,5.00000,0.20000]</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：equations &#x3D; [[&quot;a&quot;,&quot;b&quot;]], values &#x3D; [0.5], queries &#x3D; [[&quot;a&quot;,&quot;b&quot;],[&quot;b&quot;,&quot;a&quot;],[&quot;a&quot;,&quot;c&quot;],[&quot;x&quot;,&quot;y&quot;]]</span><br><span class="line">输出：[0.50000,2.00000,-1.00000,-1.00000]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= equations.length &lt;= 20</code></li>
<li><code>equations[i].length == 2</code></li>
<li><code>1 &lt;= Ai.length, Bi.length &lt;= 5</code></li>
<li><code>values.length == equations.length</code></li>
<li><code>0.0 &lt; values[i] &lt;= 20.0</code></li>
<li><code>1 &lt;= queries.length &lt;= 20</code></li>
<li><code>queries[i].length == 2</code></li>
<li><code>1 &lt;= Cj.length, Dj.length &lt;= 5</code></li>
<li><code>Ai, Bi, Cj, Dj</code> 由小写英文字母与数字组成</li>
</ul>
<p>并查集</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string[][]&#125;</span> <span class="variable">equations</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">values</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string[][]&#125;</span> <span class="variable">queries</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[]&#125;</span></span></span></span><br><span class="line"><span class="comment"> * 并查集</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> calcEquation = <span class="function"><span class="keyword">function</span>(<span class="params">equations, values, queries</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 父集 存储变量之间的映射关系</span></span><br><span class="line">    <span class="keyword">let</span> parentMap = <span class="keyword">new</span> <span class="built_in">Map</span>();</span><br><span class="line">    <span class="comment">// 存储各个变量之间的比例关系</span></span><br><span class="line">    <span class="keyword">let</span> valueMap = <span class="keyword">new</span> <span class="built_in">Map</span>();</span><br><span class="line">    <span class="comment">// 遍历每个等式，构造并查集</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; equations.length; i++) &#123;</span><br><span class="line">        <span class="comment">// 预处理</span></span><br><span class="line">        <span class="comment">// 本身未有的数，设为自己的根节点</span></span><br><span class="line">        <span class="keyword">if</span> (!parentMap.has(equations[i][<span class="number">0</span>])) &#123;</span><br><span class="line">            parentMap.set(equations[i][<span class="number">0</span>], equations[i][<span class="number">0</span>]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (!parentMap.has(equations[i][<span class="number">1</span>])) &#123;</span><br><span class="line">            parentMap.set(equations[i][<span class="number">1</span>], equations[i][<span class="number">1</span>]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 本身未有的数，权重初始化为1</span></span><br><span class="line">        <span class="keyword">if</span> (!valueMap.has(equations[i][<span class="number">0</span>])) &#123;</span><br><span class="line">            valueMap.set(equations[i][<span class="number">0</span>], <span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (!valueMap.has(equations[i][<span class="number">1</span>])) &#123;</span><br><span class="line">            valueMap.set(equations[i][<span class="number">1</span>], <span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 家里并查集</span></span><br><span class="line">        union(parentMap, valueMap, equations[i][<span class="number">0</span>], equations[i][<span class="number">1</span>], values[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 结果</span></span><br><span class="line">    <span class="keyword">const</span> result = [];</span><br><span class="line">    <span class="comment">// 根据问题进行查询</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; queries.length; i++) &#123;</span><br><span class="line">        <span class="comment">// 查找两数</span></span><br><span class="line">        <span class="keyword">let</span> tmp1 = find(parentMap, valueMap, queries[i][<span class="number">0</span>]);</span><br><span class="line">        <span class="keyword">let</span> tmp2 = find(parentMap, valueMap, queries[i][<span class="number">1</span>]);</span><br><span class="line">        <span class="comment">// 未找到两数之一</span></span><br><span class="line">        <span class="keyword">if</span> (!tmp1 || !tmp2) &#123;</span><br><span class="line">            result.push(-<span class="number">1.0</span>);</span><br><span class="line">            <span class="keyword">continue</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (tmp1.index === tmp2.index) &#123;</span><br><span class="line">            <span class="comment">// 在同一个并查集中</span></span><br><span class="line">            result.push(tmp1.value / tmp2.value);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">// 不在同一个并查集中</span></span><br><span class="line">            result.push(-<span class="number">1.0</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result;</span><br><span class="line">&#125;;</span><br><span class="line"><span class="comment">// 合并index1和index2对应的集</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">union</span>(<span class="params">parentMap, valueMap, index1, index2, value</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> tmp1 = find(parentMap, valueMap, index1);</span><br><span class="line">    <span class="keyword">let</span> tmp2 = find(parentMap, valueMap, index2);</span><br><span class="line">    parentMap.set(tmp1.index, tmp2.index);</span><br><span class="line">    valueMap.set(tmp1.index, (value * tmp2.value) / tmp1.value);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">find</span>(<span class="params">parentMap, valueMap, index</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> value = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span> (parentMap.get(index) &amp;&amp; parentMap.get(index) !== index) &#123;</span><br><span class="line">        value *= valueMap.get(index);</span><br><span class="line">        index = parentMap.get(index);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (!parentMap.get(index)) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> &#123;</span><br><span class="line">        index,</span><br><span class="line">        value</span><br><span class="line">    &#125;;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>DFS</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string[][]&#125;</span> <span class="variable">equations</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">values</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string[][]&#125;</span> <span class="variable">queries</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[]&#125;</span></span></span></span><br><span class="line"><span class="comment"> * 深度优先遍历</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">var</span> calcEquation = <span class="function"><span class="keyword">function</span>(<span class="params">equations, values, queries</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 结果</span></span><br><span class="line">    <span class="keyword">let</span> res = [];</span><br><span class="line">    <span class="comment">// 已经访问过</span></span><br><span class="line">    <span class="keyword">let</span> already = [];</span><br><span class="line">    <span class="comment">// 判断是否访问过</span></span><br><span class="line">    <span class="keyword">let</span> visited = <span class="keyword">new</span> <span class="built_in">Array</span>(values.length).fill(<span class="literal">false</span>);</span><br><span class="line">    <span class="comment">// 遍历所有等式</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> item <span class="keyword">of</span> equations)&#123;</span><br><span class="line">        <span class="comment">// 没有访问过该数</span></span><br><span class="line">        <span class="keyword">if</span>(already.indexOf(item[<span class="number">0</span>]) === -<span class="number">1</span>) already.push(item[<span class="number">0</span>]);</span><br><span class="line">        <span class="keyword">if</span>(already.indexOf(item[<span class="number">1</span>]) === -<span class="number">1</span>) already.push(item[<span class="number">1</span>]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> item <span class="keyword">of</span> queries) &#123;</span><br><span class="line">        <span class="comment">// 找不到其中的数</span></span><br><span class="line">        <span class="keyword">if</span> (already.indexOf(item[<span class="number">0</span>]) === -<span class="number">1</span> || already.indexOf(item[<span class="number">1</span>]) === -<span class="number">1</span>)</span><br><span class="line">            res.push(-<span class="number">1.0</span>);</span><br><span class="line">        <span class="comment">// 相等的数</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (item[<span class="number">0</span>] === item[<span class="number">1</span>])</span><br><span class="line">            res.push(<span class="number">1.0</span>);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">// let visited=new Array(values.length).fill(false);</span></span><br><span class="line">            res.push(backtracking(visited, <span class="number">0</span>, item[<span class="number">0</span>], item[<span class="number">1</span>])[<span class="number">0</span>]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">backtracking</span>(<span class="params">visited, i, head, tail</span>)</span>&#123;</span><br><span class="line">        <span class="keyword">let</span> ans = [<span class="number">1.0</span>, <span class="literal">false</span>];</span><br><span class="line">        <span class="keyword">if</span> (i === values.length) <span class="keyword">return</span> [-<span class="number">1.0</span>, <span class="literal">false</span>];</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">let</span> j = <span class="number">0</span>, len = values.length; j &lt; len; j++)&#123;</span><br><span class="line">            <span class="keyword">if</span> (equations[j][<span class="number">0</span>] === tail &amp;&amp; equations[j][<span class="number">1</span>] === head)&#123;</span><br><span class="line">                ans[<span class="number">0</span>] *= <span class="number">1</span> / values[j];</span><br><span class="line">                <span class="keyword">return</span> [ans[<span class="number">0</span>], <span class="literal">true</span>];</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>((equations[j][<span class="number">0</span>] !== head &amp;&amp; equations[j][<span class="number">1</span>] !== head) || visited[j]) <span class="keyword">continue</span>;</span><br><span class="line"></span><br><span class="line">            visited[j] = <span class="literal">true</span>;</span><br><span class="line">            <span class="keyword">let</span> store = ans[<span class="number">0</span>];</span><br><span class="line">            ans[<span class="number">0</span>] *= equations[j][<span class="number">0</span>] === head ? values[j] : <span class="number">1</span> / values[j];</span><br><span class="line">            <span class="keyword">if</span>(equations[j][<span class="number">1</span>] === tail)&#123;</span><br><span class="line">                 visited[j] = <span class="literal">false</span>;</span><br><span class="line">                 <span class="keyword">return</span> [ans[<span class="number">0</span>], <span class="literal">true</span>];</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">let</span> [a, f] = equations[j][<span class="number">0</span>] === head ? backtracking(visited, i + <span class="number">1</span>, equations[j][<span class="number">1</span>], tail): backtracking(visited,i+<span class="number">1</span>,equations[j][<span class="number">0</span>],tail);</span><br><span class="line">            <span class="keyword">if</span>(f)&#123;</span><br><span class="line">                ans[<span class="number">0</span>] *= a;</span><br><span class="line">                visited[j] = <span class="literal">false</span>;</span><br><span class="line">                <span class="keyword">return</span> [ans[<span class="number">0</span>], <span class="literal">true</span>];</span><br><span class="line">            &#125;</span><br><span class="line">            ans[<span class="number">0</span>] = store;</span><br><span class="line">            visited[j] = <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> [-<span class="number">1.0</span>, <span class="literal">false</span>];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="417-太平洋大西洋水流问题"><a href="#417-太平洋大西洋水流问题" class="headerlink" title="417. 太平洋大西洋水流问题"></a>417. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/pacific-atlantic-water-flow/">太平洋大西洋水流问题</a></h4><p>给定一个 <code>m x n</code> 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。</p>
<p>规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。</p>
<p>请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。</p>
<p><strong>提示：</strong></p>
<ol>
<li>输出坐标的顺序不重要</li>
<li><em>m</em> 和 <em>n</em> 都小于150</li>
</ol>
<p><strong>示例：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">给定下面的 5x5 矩阵:</span><br><span class="line"></span><br><span class="line">  太平洋 ~   ~   ~   ~   ~ </span><br><span class="line">       ~  1   2   2   3  (5) *</span><br><span class="line">       ~  3   2   3  (4) (4) *</span><br><span class="line">       ~  2   4  (5)  3   1  *</span><br><span class="line">       ~ (6) (7)  1   4   5  *</span><br><span class="line">       ~ (5)  1   1   2   4  *</span><br><span class="line">          *   *   *   *   * 大西洋</span><br><span class="line"></span><br><span class="line">返回:</span><br><span class="line"></span><br><span class="line">[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).</span><br></pre></td></tr></table></figure>

<p>DFS</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[][]&#125;</span> <span class="variable">matrix</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[][]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> pacificAtlantic = <span class="function"><span class="keyword">function</span>(<span class="params">matrix</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> direction = [-<span class="number">1</span>, <span class="number">0</span>, <span class="number">1</span>, <span class="number">0</span>, -<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">if</span> (!matrix.length || !matrix[<span class="number">0</span>].length) &#123;</span><br><span class="line">        <span class="keyword">return</span> [];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">let</span> ans = [];</span><br><span class="line">    <span class="keyword">let</span> m = matrix.length, n = matrix[<span class="number">0</span>].length;</span><br><span class="line">    <span class="comment">// 左上角能到达的点</span></span><br><span class="line">    <span class="keyword">let</span> can_reach_p = <span class="built_in">Array</span>.from(<span class="built_in">Array</span>(m), <span class="function">() =&gt;</span> <span class="built_in">Array</span>(n).fill(<span class="literal">false</span>));</span><br><span class="line">    <span class="comment">// 左上角能到达的点</span></span><br><span class="line">    <span class="keyword">let</span> can_reach_a = <span class="built_in">Array</span>.from(<span class="built_in">Array</span>(m), <span class="function">() =&gt;</span> <span class="built_in">Array</span>(n).fill(<span class="literal">false</span>));</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</span><br><span class="line">        dfs(can_reach_p, i, <span class="number">0</span>);</span><br><span class="line">        dfs(can_reach_a, i, n - <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">        dfs(can_reach_p, <span class="number">0</span>, i);</span><br><span class="line">        dfs(can_reach_a, m - <span class="number">1</span>, i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (can_reach_p[i][j] &amp;&amp; can_reach_a[i][j]) &#123;</span><br><span class="line">                ans.push([i, j]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> ans; </span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">dfs</span>(<span class="params">can_reach, r, c</span>) </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (can_reach[r][c]) &#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        can_reach[r][c] = <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">let</span> x, y;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; <span class="number">4</span>; i++) &#123;</span><br><span class="line">            x = r + direction[i], y = c + direction[i+<span class="number">1</span>];</span><br><span class="line">            <span class="keyword">if</span> (x &gt;= <span class="number">0</span> &amp;&amp; x &lt; m &amp;&amp; y &gt;= <span class="number">0</span> &amp;&amp; y &lt; n &amp;&amp; matrix[r][c] &lt;= matrix[x][y]) &#123;</span><br><span class="line">                dfs(can_reach, x, y);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>BFS</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[][]&#125;</span> <span class="variable">matrix</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[][]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> pacificAtlantic = <span class="function"><span class="keyword">function</span>(<span class="params">matrix</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (!matrix || !matrix[<span class="number">0</span>]) <span class="keyword">return</span> [];</span><br><span class="line">    <span class="keyword">const</span> m = matrix.length;</span><br><span class="line">    <span class="keyword">const</span> n = matrix[<span class="number">0</span>].length;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="keyword">const</span> flag = <span class="built_in">Array</span>.from(&#123;<span class="attr">length</span>: m + <span class="number">10</span>&#125;, <span class="function">() =&gt;</span> <span class="keyword">new</span> <span class="built_in">Array</span>(n + <span class="number">10</span>).fill(<span class="number">0</span>));</span><br><span class="line">    <span class="keyword">const</span> flag2 = <span class="built_in">Array</span>.from(&#123;<span class="attr">length</span>: m + <span class="number">10</span>&#125;, <span class="function">() =&gt;</span> <span class="keyword">new</span> <span class="built_in">Array</span>(n + <span class="number">10</span>).fill(<span class="number">0</span>));</span><br><span class="line"></span><br><span class="line">    <span class="keyword">const</span> bfs = <span class="function">(<span class="params">x, y</span>) =&gt;</span> &#123;</span><br><span class="line">        <span class="keyword">const</span> q = [[x, y]];</span><br><span class="line">        flag[x][y] = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span> (q.length) &#123;</span><br><span class="line">            <span class="keyword">const</span> c = q.shift();</span><br><span class="line">            <span class="comment">// console.log(&quot;出队&quot;,c,c[0],c[1])</span></span><br><span class="line">            <span class="keyword">var</span> cx = c[<span class="number">0</span>];</span><br><span class="line">            <span class="keyword">var</span> cy = c[<span class="number">1</span>];</span><br><span class="line">            flag[cx][cy] = <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">const</span> num = matrix[cx][cy];</span><br><span class="line">         </span><br><span class="line">            <span class="keyword">var</span> shang = cx - <span class="number">1</span> &gt;= <span class="number">0</span> ? matrix[cx - <span class="number">1</span>][cy] : -<span class="number">1</span>;</span><br><span class="line">            <span class="keyword">var</span> xia = cx + <span class="number">1</span> &lt; m ? matrix[cx + <span class="number">1</span>][cy] : -<span class="number">1</span>;       </span><br><span class="line">            <span class="keyword">var</span> zuo = cy - <span class="number">1</span> &gt;= <span class="number">0</span> ? matrix[cx][cy - <span class="number">1</span>] : -<span class="number">1</span>;</span><br><span class="line">            <span class="keyword">var</span> you = cy + <span class="number">1</span> &lt; n ? matrix[cx][cy + <span class="number">1</span>] : -<span class="number">1</span>;</span><br><span class="line">          </span><br><span class="line">            <span class="keyword">if</span> (shang &gt;= num &amp;&amp; flag[cx - <span class="number">1</span>][cy] === <span class="number">0</span>)&#123;</span><br><span class="line">                flag[cx - <span class="number">1</span>][cy] = <span class="number">1</span>;</span><br><span class="line">                q.push([cx - <span class="number">1</span>, cy]);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (xia &gt;= num &amp;&amp; flag[cx + <span class="number">1</span>][cy] === <span class="number">0</span>)&#123;</span><br><span class="line">                flag[cx + <span class="number">1</span>][cy] = <span class="number">1</span>;</span><br><span class="line">                q.push([cx + <span class="number">1</span>, cy]);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(zuo&gt;=num&amp;&amp;flag[cx][cy-<span class="number">1</span>]==<span class="number">0</span>)&#123;</span><br><span class="line">                flag[cx][cy-<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line">                q.push([cx,cy-<span class="number">1</span>]);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(you &gt;= num &amp;&amp; flag[cx][cy + <span class="number">1</span>] == <span class="number">0</span>)&#123;</span><br><span class="line">                flag[cx][cy + <span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line">                q.push([cx, cy + <span class="number">1</span>]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">const</span> bfs2 = <span class="function">(<span class="params">x, y</span>) =&gt;</span> &#123;</span><br><span class="line">        <span class="keyword">const</span> q = [[x, y]];</span><br><span class="line">        flag2[x][y] = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span> (q.length) &#123;</span><br><span class="line">            <span class="keyword">const</span> c = q.shift();</span><br><span class="line">            <span class="keyword">var</span> cx = c[<span class="number">0</span>];</span><br><span class="line">            <span class="keyword">var</span> cy = c[<span class="number">1</span>];</span><br><span class="line">            flag2[cx][cy] = <span class="number">1</span>;</span><br><span class="line">           </span><br><span class="line">            <span class="keyword">const</span> num = matrix[cx][cy];</span><br><span class="line">            <span class="keyword">var</span> shang = cx - <span class="number">1</span> &gt;= <span class="number">0</span> ? matrix[cx - <span class="number">1</span>][cy] : -<span class="number">1</span>;</span><br><span class="line">            <span class="keyword">var</span> xia = cx + <span class="number">1</span>&lt; m ? matrix[cx + <span class="number">1</span>][cy] :-<span class="number">1</span>;      </span><br><span class="line">            <span class="keyword">var</span> zuo = cy - <span class="number">1</span> &gt;= <span class="number">0</span> ? matrix[cx][cy - <span class="number">1</span>] : -<span class="number">1</span>;</span><br><span class="line">            <span class="keyword">var</span> you = cy + <span class="number">1</span> &lt; n ? matrix[cx][cy + <span class="number">1</span>] : -<span class="number">1</span>;</span><br><span class="line">            <span class="keyword">if</span>(shang &gt;= num &amp;&amp; flag2[cx - <span class="number">1</span>][cy] === <span class="number">0</span>)&#123;</span><br><span class="line">                flag2[cx - <span class="number">1</span>][cy] = <span class="number">1</span>;</span><br><span class="line">                q.push([cx - <span class="number">1</span>, cy]);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(xia &gt;= num &amp;&amp; flag2[cx + <span class="number">1</span>][cy] === <span class="number">0</span>)&#123;</span><br><span class="line">                flag2[cx + <span class="number">1</span>][cy] = <span class="number">1</span>;</span><br><span class="line">                q.push([cx + <span class="number">1</span>, cy]);</span><br><span class="line">             </span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(zuo &gt;= num &amp;&amp; flag2[cx][cy - <span class="number">1</span>] === <span class="number">0</span>)&#123;</span><br><span class="line">                flag2[cx][cy - <span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line">                q.push([cx, cy - <span class="number">1</span>]);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(you &gt;= num &amp;&amp; flag2[cx][cy + <span class="number">1</span>] === <span class="number">0</span>)&#123;</span><br><span class="line">                flag2[cx][cy + <span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line">                q.push([cx, cy + <span class="number">1</span>]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; n; i++)&#123;</span><br><span class="line">        bfs(<span class="number">0</span>, i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; m; i++)&#123;</span><br><span class="line">        bfs(i, <span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i=<span class="number">0</span>;i&lt;m;i++)&#123;</span><br><span class="line">        bfs2(i, n - <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; n; i++)&#123;</span><br><span class="line">        bfs2(m - <span class="number">1</span>, i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">const</span> qq = [];</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; m; i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; n; j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(flag[i][j] + flag2[i][j] === <span class="number">2</span>)&#123;</span><br><span class="line">                qq.push([i, j]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> qq;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="547-省份数量"><a href="#547-省份数量" class="headerlink" title="547. 省份数量"></a>547. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/number-of-provinces/">省份数量</a></h4><p>有 <code>n</code> 个城市，其中一些彼此相连，另一些没有相连。如果城市 <code>a</code> 与城市 <code>b</code> 直接相连，且城市 <code>b</code> 与城市 <code>c</code> 直接相连，那么城市 <code>a</code> 与城市 <code>c</code> 间接相连。</p>
<p><strong>省份</strong> 是一组直接或间接相连的城市，组内不含其他没有相连的城市。</p>
<p>给你一个 <code>n x n</code> 的矩阵 <code>isConnected</code> ，其中 <code>isConnected[i][j] = 1</code> 表示第 <code>i</code> 个城市和第 <code>j</code> 个城市直接相连，而 <code>isConnected[i][j] = 0</code> 表示二者不直接相连。</p>
<p>返回矩阵中 <strong>省份</strong> 的数量。</p>
<p><strong>示例 1：</strong></p>
<p><img data-src="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210803000409.jpeg" alt="img"></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：isConnected &#x3D; [[1,1,0],[1,1,0],[0,0,1]]</span><br><span class="line">输出：2</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<p><img data-src="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210803083157.jpeg" alt="img"></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：isConnected &#x3D; [[1,0,0],[0,1,0],[0,0,1]]</span><br><span class="line">输出：3</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= n &lt;= 200</li>
<li>n == isConnected.length</li>
<li>n == isConnected[i].length</li>
<li>isConnected[i][j] 为 1 或 0</li>
<li>isConnected[i][i] == 1</li>
<li>isConnected[i][j] == isConnected[j][i]</li>
</ul>
<p>DFS</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[][]&#125;</span> <span class="variable">M</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> findCircleNum = <span class="function"><span class="keyword">function</span>(<span class="params">M</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> n = M.length;</span><br><span class="line">    <span class="keyword">if</span> (!n) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">let</span> count = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">let</span> isVisited = <span class="keyword">new</span> <span class="built_in">Array</span>(n).fill(<span class="literal">false</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (!isVisited[i]) &#123;</span><br><span class="line">            dfs(i);</span><br><span class="line">            count++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> count;</span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">dfs</span>(<span class="params">i</span>) </span>&#123;</span><br><span class="line">        isVisited[i] = <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!isVisited[j] &amp;&amp; M[i][j]) &#123;</span><br><span class="line">                dfs(j);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>或者用set存储</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[][]&#125;</span> <span class="variable">M</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> * 深度优先搜索</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> findCircleNum = <span class="function"><span class="keyword">function</span>(<span class="params">M</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 已访问的省份数</span></span><br><span class="line">    <span class="keyword">let</span> visited = <span class="keyword">new</span> <span class="built_in">Set</span>();</span><br><span class="line">    <span class="comment">// 集的个数</span></span><br><span class="line">    <span class="keyword">let</span> count = <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// 遍历每行</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; M.length; i++) &#123;</span><br><span class="line">        <span class="comment">// 检查第i个城市是否已访问过</span></span><br><span class="line">        <span class="keyword">if</span> (!visited.has(i)) &#123;</span><br><span class="line">            <span class="comment">// 未访问过i，进行深度遍历搜索</span></span><br><span class="line">            dfs(M, visited, i);</span><br><span class="line">            count++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> count;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 深度优先搜索原矩阵</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">dfs</span>(<span class="params">M, visited, i</span>) </span>&#123; </span><br><span class="line">    <span class="comment">// 遍历改行</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; M.length; j++) &#123;</span><br><span class="line">        <span class="comment">// i与j联通，且没有访问过</span></span><br><span class="line">        <span class="keyword">if</span> (M[i][j] == <span class="number">1</span> &amp;&amp; !visited.has(j)) &#123;</span><br><span class="line">            visited.add(j);</span><br><span class="line">            dfs(M, visited, j);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>BFS</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[][]&#125;</span> <span class="variable">M</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> * 广度优先搜索</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> findCircleNum = <span class="function"><span class="keyword">function</span>(<span class="params">M</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 省份数量</span></span><br><span class="line">    <span class="keyword">const</span> provinces = M.length;</span><br><span class="line">    <span class="comment">// 已遍历的</span></span><br><span class="line">    <span class="keyword">const</span> visited = <span class="keyword">new</span> <span class="built_in">Set</span>();</span><br><span class="line">    <span class="comment">// 图的个数</span></span><br><span class="line">    <span class="keyword">let</span> circles = <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// 队列</span></span><br><span class="line">    <span class="keyword">const</span> queue = <span class="keyword">new</span> <span class="built_in">Array</span>();</span><br><span class="line">    <span class="comment">// 遍历各行</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; provinces; i++) &#123;</span><br><span class="line">        <span class="comment">// 未访问该省</span></span><br><span class="line">        <span class="keyword">if</span> (!visited.has(i)) &#123;</span><br><span class="line">            queue.push(i);</span><br><span class="line">            <span class="keyword">while</span> (queue.length) &#123;</span><br><span class="line">                <span class="comment">// 首页</span></span><br><span class="line">                <span class="keyword">const</span> j = queue.shift();</span><br><span class="line">                visited.add(j);</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">let</span> k = <span class="number">0</span>; k &lt; provinces; k++) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (M[j][k] === <span class="number">1</span> &amp;&amp; !visited.has(k)) &#123;</span><br><span class="line">                        queue.push(k);</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            circles++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> circles;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>并查集</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[][]&#125;</span> <span class="variable">M</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> * 并查集</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> findCircleNum = <span class="function"><span class="keyword">function</span>(<span class="params">isConnected</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> provinces = isConnected.length;</span><br><span class="line">    <span class="keyword">const</span> parent = <span class="keyword">new</span> <span class="built_in">Array</span>(provinces).fill(<span class="number">0</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; provinces; i++) &#123;</span><br><span class="line">        parent[i] = i;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; provinces; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> j = i + <span class="number">1</span>; j &lt; provinces; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (isConnected[i][j] == <span class="number">1</span>) &#123;</span><br><span class="line">                union(parent, i, j);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">let</span> circles = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; provinces; i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (parent[i] === i) &#123;</span><br><span class="line">            circles++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> circles;</span><br><span class="line">&#125;;</span><br><span class="line"><span class="comment">// 并</span></span><br><span class="line"><span class="keyword">const</span> union = <span class="function">(<span class="params">parent, index1, index2</span>) =&gt;</span> &#123;</span><br><span class="line">    parent[find(parent, index1)] = find(parent, index2);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 查找</span></span><br><span class="line"><span class="keyword">const</span> find = <span class="function">(<span class="params">parent, index</span>) =&gt;</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (parent[index] !== index) &#123;</span><br><span class="line">        parent[index] = find(parent, parent[index]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> parent[index];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="695-岛屿的最大面积"><a href="#695-岛屿的最大面积" class="headerlink" title="695. 岛屿的最大面积"></a>695. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/max-area-of-island/">岛屿的最大面积</a></h4><p>给定一个包含了一些 <code>0</code> 和 <code>1</code> 的非空二维数组 <code>grid</code> 。</p>
<p>一个 <strong>岛屿</strong> 是由一些相邻的 <code>1</code> (代表土地) 构成的组合，这里的「相邻」要求两个 <code>1</code> 必须在水平或者竖直方向上相邻。你可以假设 <code>grid</code> 的四个边缘都被 <code>0</code>（代表水）包围着。</p>
<p>找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 <code>0</code> 。)</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">[[0,0,1,0,0,0,0,1,0,0,0,0,0],</span><br><span class="line"> [0,0,0,0,0,0,0,1,1,1,0,0,0],</span><br><span class="line"> [0,1,1,0,1,0,0,0,0,0,0,0,0],</span><br><span class="line"> [0,1,0,0,1,1,0,0,1,0,1,0,0],</span><br><span class="line"> [0,1,0,0,1,1,0,0,1,1,1,0,0],</span><br><span class="line"> [0,0,0,0,0,0,0,0,0,0,1,0,0],</span><br><span class="line"> [0,0,0,0,0,0,0,1,1,1,0,0,0],</span><br><span class="line"> [0,0,0,0,0,0,0,1,1,0,0,0,0]]</span><br></pre></td></tr></table></figure>

<p>对于上面这个给定矩阵应返回 <code>6</code>。注意答案不应该是 <code>11</code> ，因为岛屿只能包含水平或垂直的四个方向的 <code>1</code> 。</p>
<p><strong>示例 2:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">[[0,0,0,0,0,0,0,0]]</span><br></pre></td></tr></table></figure>

<p>对于上面这个给定的矩阵, 返回 <code>0</code>。</p>
<p> <strong>注意:</strong> 给定的矩阵<code>grid</code> 的长度和宽度都不超过 50。</p>
<p>DFS </p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[][]&#125;</span> <span class="variable">grid</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> maxAreaOfIsland = <span class="function"><span class="keyword">function</span>(<span class="params">grid</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (!grid.length) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">let</span> max = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; grid.length; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; grid[i].length; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (grid[i][j] === <span class="number">0</span>) &#123;</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            max = <span class="built_in">Math</span>.max(max, dfs(i, j, <span class="number">1</span>));</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">dfs</span> (<span class="params">i, j, count</span>) </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (i &lt; <span class="number">0</span> || i &gt; grid.length - <span class="number">1</span> || j &lt; <span class="number">0</span> || j &gt; grid[i].length - <span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (grid[i][j] === <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        grid[i][j] = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">let</span> downCount = dfs(i + <span class="number">1</span>, j);</span><br><span class="line">        <span class="keyword">let</span> upCount = dfs(i - <span class="number">1</span>, j);</span><br><span class="line">        <span class="keyword">let</span> leftCount = dfs(i, j + <span class="number">1</span>);</span><br><span class="line">        <span class="keyword">let</span> rightCount = dfs(i, j - <span class="number">1</span>);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span> + downCount + upCount + leftCount + rightCount;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> max;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>BFS</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[][]&#125;</span> <span class="variable">grid</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> maxAreaOfIsland = <span class="function"><span class="keyword">function</span>(<span class="params">grid</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> row = grid.length, col = grid[<span class="number">0</span>].length;</span><br><span class="line">    <span class="keyword">let</span> direct = [[<span class="number">0</span>, <span class="number">1</span>], [<span class="number">1</span>, <span class="number">0</span>], [<span class="number">0</span>, -<span class="number">1</span>], [-<span class="number">1</span>, <span class="number">0</span>]];</span><br><span class="line">    <span class="keyword">let</span> stack = [], max = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; row; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; col; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(grid[i][j] === <span class="number">0</span>) <span class="keyword">continue</span>;</span><br><span class="line">            <span class="keyword">let</span> t = <span class="number">1</span>;</span><br><span class="line">            stack.push([i, j]);</span><br><span class="line">            grid[i][j] = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">while</span>(stack.length &gt; <span class="number">0</span>) &#123;</span><br><span class="line">                <span class="keyword">let</span> [x, y] = stack.pop();</span><br><span class="line">                <span class="keyword">for</span>(<span class="keyword">let</span> k = <span class="number">0</span>; k &lt; <span class="number">4</span>; k++) &#123;</span><br><span class="line">                    <span class="keyword">let</span> newX = x + direct[k][<span class="number">0</span>];</span><br><span class="line">                    <span class="keyword">let</span> newY = y + direct[k][<span class="number">1</span>];</span><br><span class="line">                    <span class="keyword">if</span>(newX &gt;= <span class="number">0</span> &amp;&amp; newY &gt;= <span class="number">0</span> &amp;&amp; newX &lt; row &amp;&amp; newY &lt; col &amp;&amp; grid[newX][newY] === <span class="number">1</span>) &#123;</span><br><span class="line">                        grid[newX][newY] = <span class="number">0</span>;</span><br><span class="line">                        stack.push([newX, newY]);</span><br><span class="line">                        t++;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            max = <span class="built_in">Math</span>.max(max, t);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> max;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="寻找和为定值的多个数"><a href="#寻找和为定值的多个数" class="headerlink" title="寻找和为定值的多个数"></a>寻找和为定值的多个数</h4><p>题目描述</p>
<p>输入两个整数n和sum，从数列1，2，3…….n 中随意取几个数，使其和等于sum，要求将其中所有的可能组合列出来。</p>
<p>解法</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">getAllCombin</span>(<span class="params">array, n, sum, temp</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (temp.length === n) &#123;</span><br><span class="line">        <span class="keyword">if</span> (temp.reduce(<span class="function">(<span class="params">t, c</span>) =&gt;</span> t + c) === sum) &#123;</span><br><span class="line">            <span class="keyword">return</span> temp;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; array.length; i++) &#123;</span><br><span class="line">        <span class="keyword">const</span> current = array.shift();</span><br><span class="line">        temp.push(current);</span><br><span class="line">        <span class="keyword">const</span> result = getAllCombin(array, n, sum, temp);</span><br><span class="line">        <span class="keyword">if</span> (result) &#123;</span><br><span class="line">            <span class="keyword">return</span> result;</span><br><span class="line">        &#125;</span><br><span class="line">        temp.pop();</span><br><span class="line">        array.push(current);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">const</span> arr = [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>];</span><br><span class="line"></span><br><span class="line"><span class="built_in">console</span>.log(getAllCombin(arr, <span class="number">3</span>, <span class="number">10</span>, []));</span><br></pre></td></tr></table></figure>


    </div>

    
    
    
      
<div>
        <div style="text-align:center;color: #ccc;font-size:14px;">-------------本文结束<i class="fa fa-paw"></i>感谢您的阅读-------------</div>
</div>
        

  <div class="followme">
    <p>欢迎关注我的其它发布渠道</p>

    <div class="social-list">

        <div class="social-item">
          <a target="_blank" class="social-link" href="/atom.xml">
            <span class="icon">
              <i class="fa fa-rss"></i>
            </span>

            <span class="label">RSS</span>
          </a>
        </div>
    </div>
  </div>


      <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/javascript/" rel="tag"><i class="fa fa-tag"></i> javascript</a>
              <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/" rel="tag"><i class="fa fa-tag"></i> 数据结构和算法</a>
              <a href="/tags/BFS%E3%80%81DFS-%E5%9B%9E%E6%BA%AF%E6%B3%95/" rel="tag"><i class="fa fa-tag"></i> BFS、DFS 回溯法</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/2021/03/09/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E5%88%B7%E9%A2%98/" rel="prev" title="二分查找刷题">
      <i class="fa fa-chevron-left"></i> 二分查找刷题
    </a></div>
      <div class="post-nav-item">
    <a href="/2021/03/09/HTML%E5%92%8C%E6%B5%8F%E8%A7%88%E5%99%A8/" rel="next" title="HTML和浏览器">
      HTML和浏览器 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          
    <div class="comments" id="valine-comments"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%B8%93%E9%A2%98%E9%83%A8%E5%88%86"><span class="nav-text">专题部分</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#BFS%E3%80%81DFS-%E5%9B%9E%E6%BA%AF%E6%B3%95"><span class="nav-text">BFS、DFS 回溯法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#17-%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88"><span class="nav-text">17. 电话号码的字母组合</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#22-%E6%8B%AC%E5%8F%B7%E7%94%9F%E6%88%90"><span class="nav-text">22. 括号生成</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#39-%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C"><span class="nav-text">39. 组合总和</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#46-%E5%85%A8%E6%8E%92%E5%88%97"><span class="nav-text">46. 全排列</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#47-%E5%85%A8%E6%8E%92%E5%88%97-II"><span class="nav-text">47. 全排列 II</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#51-N-%E7%9A%87%E5%90%8E"><span class="nav-text">51. N 皇后</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#52-N%E7%9A%87%E5%90%8E-II"><span class="nav-text">52. N皇后 II</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#78-%E5%AD%90%E9%9B%86"><span class="nav-text">78. 子集</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#79-%E5%8D%95%E8%AF%8D%E6%90%9C%E7%B4%A2"><span class="nav-text">79. 单词搜索</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#200-%E5%B2%9B%E5%B1%BF%E6%95%B0%E9%87%8F"><span class="nav-text">200. 岛屿数量</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#207-%E8%AF%BE%E7%A8%8B%E8%A1%A8"><span class="nav-text">207. 课程表</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#301-%E5%88%A0%E9%99%A4%E6%97%A0%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7"><span class="nav-text">301. 删除无效的括号</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#399-%E9%99%A4%E6%B3%95%E6%B1%82%E5%80%BC"><span class="nav-text">399. 除法求值</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#417-%E5%A4%AA%E5%B9%B3%E6%B4%8B%E5%A4%A7%E8%A5%BF%E6%B4%8B%E6%B0%B4%E6%B5%81%E9%97%AE%E9%A2%98"><span class="nav-text">417. 太平洋大西洋水流问题</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#547-%E7%9C%81%E4%BB%BD%E6%95%B0%E9%87%8F"><span class="nav-text">547. 省份数量</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#695-%E5%B2%9B%E5%B1%BF%E7%9A%84%E6%9C%80%E5%A4%A7%E9%9D%A2%E7%A7%AF"><span class="nav-text">695. 岛屿的最大面积</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%AF%BB%E6%89%BE%E5%92%8C%E4%B8%BA%E5%AE%9A%E5%80%BC%E7%9A%84%E5%A4%9A%E4%B8%AA%E6%95%B0"><span class="nav-text">寻找和为定值的多个数</span></a></li></ol></li></ol></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="hxy"
      src="/images/Robben.gif">
  <p class="site-author-name" itemprop="name">hxy</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">80</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">8</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">120</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/huxingyi1997" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;huxingyi1997" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:huxingyi1997@zju.edu.cn" title="E-Mail → mailto:huxingyi1997@zju.edu.cn" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
  </div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-frog"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">hxy</span>
</div>

<div class="theme-info">
  <div class="powered-by"></div>
  <span class="post-count">博客全站共1039.2k字</span>
</div>

        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/lozad@1/dist/lozad.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>




  




  
<script src="/js/local-search.js"></script>













  

  


<script>
NexT.utils.loadComments(document.querySelector('#valine-comments'), () => {
  NexT.utils.getScript('//unpkg.com/valine/dist/Valine.min.js', () => {
    var GUEST = ['nick', 'mail', 'link'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(item => {
      return GUEST.includes(item);
    });
    new Valine({
      el         : '#valine-comments',
      verify     : false,
      notify     : true,
      appId      : 'pQsO3ySbU4VtWN2j1FLA74Ha-gzGzoHsz',
      appKey     : 'QYacMDY2VY7Wazprg1X6FiUv',
      placeholder: "Just go go",
      avatar     : 'mm',
      meta       : guest,
      pageSize   : '10' || 10,
      visitor    : false,
      lang       : 'zh-cn' || 'zh-cn',
      path       : location.pathname,
      recordIP   : false,
      serverURLs : ''
    });
  }, window.Valine);
});
</script>

  
  <!-- 动态背景特效 -->
  <!-- 樱花特效 -->
    <script async src="/js/src/sakura.js"></script>
    <script async src="/js/src/fairyDustCursor.js"></script>
</body>
</html>
